#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int longestValidParentheses(string s)
    {
        int n = s.size();
        vector<int> dp(n);

        int len = 0;
        for (int i = 1; i < n; i++)
        {
            if (s[i] == ')')
            {
                if (s[i - 1] == '(')
                {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(')
                {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                len = max(len, dp[i]);
            }
        }

        return len;
    }
};